package com.lx.algorithm.morris;

import com.lx.algorithm.Tree.Tree;
import com.lx.algorithm.radix.RadixSort;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-21 23:42:17
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-21     张李鑫                     1.0         1.0 Version
 */
public class Morris {

    static class Node<T> {
        T value;
        Node left;
        Node right;

        public Node(T value) {
            this.value = value;
        }
    }

    public static void pre(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.value);
        pre(node.left);
        pre(node.right);
    }

    public static void in(Node node) {
        if (node == null) {
            return;
        }
        in(node.left);
        System.out.print(node.value);
        in(node.right);
    }


    public static void order(Node node) {
        if (node == null) {
            return;
        }
        order(node.left);
        order(node.right);
        System.out.print(node.value);
    }

    /**
     * 1）如果cur没有左孩子，cur向右移动(cur = cur.right)
     * 2）如果cur有左孩子，找到左子树上最右的节点mostRight：
     * a.如果mostRight的右指针指向空，让其指向cur，
     * 然后cur向左移动(cur = cur.left)
     * b.如果mostRight的右指针指向cur，让其指向null，
     * 然后cur向右移动(cur = cur.right)
     * 3）cur为空时遍历停止
     *
     * @param node
     */
    public static void morris(Node node) {
        if (node == null) {
            return;
        }
        Node cur = node;
        Node morrisRight = null;
        while (cur != null) {
            morrisRight = cur.left;
            if (morrisRight != null) {
                while (morrisRight.right != null && morrisRight.right != cur) {
                    morrisRight = morrisRight.right;
                }
                if (morrisRight.right == null) {
                    morrisRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    morrisRight.right = null;
                }
            }
            cur = cur.right;
        }
    }

    /**
     * morris 会返回头节点两次 所以对一次遇到就打 如果不能返回两次的遇到就打
     * 其余节点遇到就打
     *
     * @param node
     */
    public static void morrisPre(Node node) {
        if (node == null) {
            return;
        }
        Node cur = node;
        Node morrisRight = null;
        while (cur != null) {
            morrisRight = cur.left;
            if (morrisRight != null) {
                while (morrisRight.right != null && morrisRight.right != cur) {
                    morrisRight = morrisRight.right;
                }
                if (morrisRight.right == null) {
                    //满足这个条件说明要指向头结点 所以打
                    System.out.print(cur.value);
                    morrisRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    morrisRight.right = null;
                }
            }else {
                //没有左树 说明只能到达这个节点一次 遇到就打印
                System.out.print(cur.value);
            }
            cur = cur.right;
        }
    }

    /**
     * morris 会返回头节点两次 所以头结点等回来的时候在打
     * 其余节点遇到就打
     *
     * @param node
     */
    public static void morrisIn(Node node) {
        if (node == null) {
            return;
        }
        Node cur = node;
        Node morrisRight = null;
        while (cur != null) {
            morrisRight = cur.left;
            if (morrisRight != null) {
                while (morrisRight.right != null && morrisRight.right != cur) {
                    morrisRight = morrisRight.right;
                }
                if (morrisRight.right == null) {
                    morrisRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    morrisRight.right = null;
                }
            }
            System.out.print(cur.value);
            cur = cur.right;
        }
    }

    /**
     * 后续遍历:
     * 逆序打印左树的右边界
     * @param node
     */
    public static void morrisOrder(Node node) {
        if (node == null) {
            return;
        }
        Node cur = node;
        Node morrisRight = null;
        while (cur != null) {
            morrisRight = cur.left;
            if (morrisRight != null) {
                while (morrisRight.right != null && morrisRight.right != cur) {
                    morrisRight = morrisRight.right;
                }
                if (morrisRight.right == null) {
                    morrisRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    morrisRight.right = null;
                    //每次回去的时候都打印左树的右边界
                    print(cur.left);
                }
            }
            cur = cur.right;
        }
        print(node);
    }

    public static void print(Node node){
        Node reverse = reverse(node);
        Node cur=reverse;
        while (cur!=null){
            System.out.print(cur.value);
            cur=cur.right;
        }
        reverse(reverse);
    }

    public static Node reverse(Node node){
        Node cur=null;
        Node next=null;
        while (node!=null){
            cur=node.right;
            node.right=next;
            next=node;
            node=cur;
        }
        return next;
    }

    public static void main(String[] args) {
        Node<Integer> a = new Node<>(1);
        Node<Integer> b = new Node<>(2);
        Node<Integer> c = new Node<>(3);
        Node<Integer> d = new Node<>(4);
        Node<Integer> e = new Node<>(5);
        Node<Integer> f = new Node<>(6);
        Node<Integer> g = new Node<>(7);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
        morrisPre(a);
        System.out.println();
        pre(a);
        System.out.println();
        in(a);
        System.out.println();
        morrisIn(a);
        System.out.println();
        order(a);
        System.out.println();
        morrisOrder(a);
    }
}